package com.snopy.leetcode.index1_1000.index301_400;

import java.util.Arrays;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question307
 * @description 区域和检索-数组可修改
 * 给你一个数组 nums ，请你完成两类查询。
 *
 * 其中一类查询要求 更新 数组nums下标对应的值
 * 另一类查询要求返回数组nums中索引left和索引right之间（包含）的nums元素的 和，其中left <= right
 * 实现 NumArray 类：
 *
 * NumArray(int[] nums) 用整数数组 nums 初始化对象
 * void update(int index, int val) 将 nums[index] 的值 更新 为 val
 * int sumRange(int left, int right) 返回数组nums中索引left和索引right之间（包含）的nums元素的 和（即，nums[left] + nums[left + 1], ..., nums[right]）
 * 
 * 示例 1：
 *
 * 输入：
 * ["NumArray", "sumRange", "update", "sumRange"]
 * [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
 * 输出：
 * [null, 9, null, 8]
 *
 * 解释：
 * NumArray numArray = new NumArray([1, 3, 5]);
 * numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
 * numArray.update(1, 2);   // nums = [1,2,5]
 * numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
 *
 * @email 77912204@qq.com
 * @date 2022/04/04 19:03
 */
public class Question307 {
    public static void main(String[] args) {

        NumArray nums = new NumArray(new int[]{1,3,5});
        int sum = nums.sumRange(0, 2);
        System.out.println(sum);
        nums.update(1, 2);
        sum = nums.sumRange(0, 2);
        System.out.println(sum);
    }
}
class NumArray {
    private int[] nums;
    private int size;
    private int[] sums;
    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        size = (int)Math.sqrt(n);
        sums = new int[n+size-1/size];
        for (int i=0;i<n;i++){
            sums[i / size] +=nums[i];
        }
    }

    public void update(int index, int val) {
        sums[index/size]+=val-nums[index];
        this.nums[index] = val;
    }

    public int sumRange(int left, int right) {

        int sl = left/size,sr = right/size,il = left%size,ir = right%size;
        int sum = 0;
        if (sl==sr){
            for (int i = left; i <= right; i++) {
                sum+=nums[i];
            }
            return sum;
        }
        int sum0 = 0;
        for (int i = il;i<size;i++){
            sum0+=nums[size*sl+i];
        }
        int sum1 = 0;
        for (int i = sl+1;i<sr;i++){
            sum1+=sums[i];
        }
        int sum2 = 0;
        for (int i=0;i<=ir;i++){
            sum2+=nums[sr*size+i];
        }
        sum = sum0 + sum1 + sum2;
        return sum;
    }
}